/* 
 * File:   Graph.h
 * Author: lusitanio
 *
 * Created on 16 de Fevereiro de 2012, 15:41
 */

#ifndef GRAPH_H
#define	GRAPH_H

#include <vector>
#include "Sensor_Info.h"

#define INFINITO 99999
#define MEMBER 1
#define NONMEMBER 0

class Graph {
private:
    float** arcs;
    int size;

    void allocArrays() {
        arcs = new float*[size];
        for (int i = 0; i < size; i++) {
            arcs[i] = new float[size];
        }
    }

public:

    Graph(int nelems=1) {
        size = nelems;
        allocArrays();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                arcs[i][j] = 0.0;
            }
        }
    }

    Graph(const Graph& m) {
        size = m.size;
        allocArrays();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                arcs[i][j] = m.arcs[i][j];
            }
        }

    }

    ~Graph() {
        for (int i = 0; i < size; i++) {
            delete [] arcs[i];
        }
        delete [] arcs;
    }

    Graph& operator=(const Graph &m) {
        if (this == &m) {
            // avoid self-assignment
            return *this;
        } else {
            if (this->size != m.size) {
                this->~Graph();
                size = m.size;
                allocArrays();
            }
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    arcs[i][j] = m.arcs[i][j];
                }
            }
            return *this;
        }
    }


    // cria uma aresta que "liga" (incide) em dois nós;
    // recebe o grafo e dois nós (node1 e node2)

    void addArc(int node1, int node2, float dist) {

        this->arcs[node1][node2] = dist;
        this->arcs[node2][node1] = dist;
    }

    // remove uma aresta do grafo;
    // recebe o grafo e os dois nós (node1 e node2);

    void removeArc(int node1, int node2) {

        this->arcs[node1][node2] = 0.0;
        this->arcs[node2][node1] = 0.0;
    }


    // Algoritmo dijkstra para cálculo de caminhos mais curtos em matrizes
    // de adjacencia
    // recebe grafo, nodo origem(s),nodo destino(t),número de nodos

    pair <int, int> dijkstra(int s, int t) {
        int  *perm, *path, *hops;
        int current, i, k, dc, hp;
        int newhops;
        int nexthop;
        float *dist, smalldist, newdist;
        dist = (float*) malloc(sizeof (float) * this->size);
        hops = (int*) malloc(sizeof (int) * this->size);
        perm = (int*) malloc(sizeof (int) * this->size);
        path = (int*) malloc(sizeof (int) * this->size);

        /* Inicializa todos os índices de 'perm' como 0 e de 'dist' como INFINITO */
        for (i = 0; i < this->size; i++) {
            perm[i] = NONMEMBER;
            dist[i] = INFINITO;
            hops[i] = INFINITO;
        }
        /* Inclui 's' em perm (perm[s]=1) e configura(armazena) sua distancia como sendo zero */
        perm[s] = MEMBER;
        dist[s] = 0;
        hops[s] = 0;
        /* define 's' como origem (fonte) da busca */
        current = s;
        k = current;
        while (current != t) {
            smalldist = INFINITO;
            dc = dist[current];
            hp = hops[current];
            for (i = 0; i < this->size; i++) {
                //se o elemento NÃO está em perm
                if (perm[i] == NONMEMBER) {
                    //calcula distância a partir do vértice corrente ao vértice adjacente i
                    if (this->arcs[current][i] > 0){
                        newdist = dc + this->arcs[current][i];
                        newhops = hp + 1;
                    }
                    else{
                        newdist = dc + INFINITO;
                        newhops = hp + INFINITO;
                    }
                    //se a distância partindo do vértice corrente for menor, atualiza o vetor
                    //de distâncias e de precedência
                    if (newdist < dist[i]) {
                        dist[i] = newdist;
                        path[i] = current;
                        hops[i] = newhops;
                    }
                    //determina o vértice (entre todos os não pertencentes a perm) com menor distância
                    if (dist[i] < smalldist) {
                        smalldist = dist[i];
                        k = i;
                    }
                }
            } /* fim for */
            /* embora estamos assumindo grafos ponderados e conexos, este if garante que
            em caso de não existência de um caminho o programa não entre em loop infinito */
            if (current == k)
                // CAMINHO NAO EXISTE
                return *new pair<int, int>(INFINITO, INFINITO);
            current = k;
            perm[current] = MEMBER;
        }/* fim while */

        int caminho = t;
        while (caminho != s) {
            nexthop = caminho;
            caminho = path[caminho];
        }
        /*/ impressao do resultado ***************
        printf("\n\nRESULTADO: ");
        caminho = t;
        printf("%d <- ", t);
        while (caminho != s){
                nexthop = caminho;
                printf("%d", path[caminho]);
                caminho = path[caminho];
                if (caminho != s)
                        printf (" <- ");
        }
        printf("\n\ncusto: %d\n\n", dist[t]);
        // ****************************************/
        pair <int, int> w_return = *new pair<int, int>(nexthop, hops[t]);
        free(dist);
        free(perm);
        free(path);
        free(hops);
        return (w_return);

    } /* fim dijkstra */

    void load_graph(std::vector<Sensor_Info> info, double range) {
        vector<Sensor_Info>::iterator x;
        vector<Sensor_Info>::iterator y;
        for (x = info.begin(); x < info.end(); x++) {
            for (y = info.begin(); y < info.end(); y++) {
                if ((*x).GetId() != (*y).GetId()) {
                    float dist = (*x).checkInRange((*y), range);
                    if (dist!=-1.0)
                        this->addArc((*x).GetId(), (*y).GetId(), 1);
                    //this->addArc((*x).GetId(), (*y).GetId(), dist);
                }
            }
        }
    }

    void print() {
        printf("**** Grafo ****\n");
        for (int i = 0; i < size; ++i) {
            printf("Sensor[%02d]: ", i);
            for (int j = 0; j < size; ++j) {
                printf("|%4.1f", arcs[i][j]);
            }
            printf("\n");
        }
        printf("********\n");
    }

};

#endif	/* GRAPH_H */

